package 二叉搜索树;

public class BinarySearchTree {
    static class TreeNode{
       public int val;
       public TreeNode left;
       public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }

    }
    public TreeNode root;
    /**
     * 查找二叉搜索树中指定的val值
     * @param val
     * @return
     */
    public  TreeNode find(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val > val) {
                cur=cur.left;
            }else if(cur.val < val) {
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }
    public void insert(int val) {
        TreeNode node =new TreeNode(val);
        if(root == null) {
            root = node;
        }else {
            TreeNode p =null;
            TreeNode cur =root;
            while (cur != null) {
                p = cur;
                //如果大于要插入的值,那么cur往左边走
                if(cur.val > val) {
                    cur = cur.left;
                }else if(cur.val < val){
                    //如果小于要插入的值，那么cur往右走
                    cur = cur.right;
                }else {
                    return;
                }
            }
            if(p.val > val) {
                p.left = node;
            }else {
                p.right = node;
            }
        }
    }
    public void InOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        InOrder(root.left);
        System.out.print(root.val+" ");
        InOrder(root.right);
    }
    public void remove(int val) {
        TreeNode cur = root;
        while (cur != null) {
         TreeNode p = cur;
         if(cur.val == val) {
             removeNode(p,cur);
         }else if(cur.val < val) {
             cur = cur.right;
         }else {
             cur = cur.left;
         }
     }
    }
    public void removeNode(TreeNode parent,TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }
            if(parent.left == cur) {
             parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }
            if(parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            //从右树找到最小值，最小值就是右树一直left直到left==null
            TreeNode target = cur.right;
            TreeNode targetP = cur;
            while (target.left != null) {
                targetP = target;
                target = target.left;
            }
            cur.val = target.val;

            if(targetP == cur) {
            //此时右树的第一个结点没有左树，说明此时的target就是最小值
                targetP.right = target.right;
            }else {
                targetP.left = target.right;
            }
        }
    }
}
